1. Field of the Invention
This invention relates to the field of broadcasting quality video data over a packet switched network in such a way that the video is played in a smooth (not jerky) manner. Further, this invention relates to video distribution systems that dynamically adjust loading of storage devices such as magnetic disks by segmenting video data objects with variable segment sizes.
2. Description of Related Art
In the past video streaming servers required that a file be fully present before the sever could start streaming the file. This imposed a considerable restriction as typical DVD or broadcast quality videos may be several Gigabytes in size and thus imposed a large latency before a viewer could start viewing a video.
Video is the most dominant medium in entertainment and is rapidly becoming a critical part of computing as well. Video is often used in CD-ROM titles, for example, to mimic personal or virtual environments, increasing an application's appeal and usability. Video has a large information carrying capacity and is heavily used in capturing and conveying complicated situations such as news events, live interviews, scientific experiments, tourist attractions, and many others.
With the increasing availability of high bandwidth networks, video on-demand applications are gaining popularity on global digital communications networks such as the Internet as well as private and corporate digital communication internal networks commonly referred to as Intranets. Example applications include online training, news broadcasts, educational programming, corporate information, and virtual seminars directly to every desktop computing system or workstation. Similarly, video kiosks can be set up in enterprises and university campuses to display live video and up-to-the-minute news, without ever needing an on-site upgrade.
Video files, however, occupy huge amounts of space on computers. It requires about 10 MB to store one minute of video in most standard compression and decompression video formats, including Motion Picture Experts Group standard MPEG-1, the Apple Computer Inc. Indio, Intel Corp. QuickTime, and Super Mac, Inc Cinema. That translates into 1.2 GB of space for two hours of video, the length of an average feature film. These tremendous storage requirements make effective on-demand sharing of video files at least as important as conventional file sharing.
However, conventional file servers do not address video's unique requirements and cannot effectively support video sharing. Full-motion video, inherited from analog TV, is a sequence of images played out at constant intervals. The two most common analog video formats are the National Television Standards Committee (NTSC), used in the United States and Japan, and Phase Alternation Standard (PAL), used in Europe. NTSC plays video at 30 frames per second, while PAL plays it at 25 frames per second. The sequence of images in a video clip must be relayed at a constant interval, or else the perceptual quality degrades rapidly: the motion jumps and the sound breaks. This rigid periodic timing property is referred to as the isochronous requirement. Referring now to FIG. 1, conventional file servers 10 are designed for minimal transfer latency. Files 15 are thus transferred to maintain the minimum latency and are transferred as quickly as possible. The files 15 will be interleaved with other digital communication traffic on the network and thus non-isochronously. Without explicit mechanisms to ensure isochronism, delivery rates are irregular, resulting in erratic playback quality at the client computing system 20.
To avoid erratic playback, the usual approach is to download whole files 15 from the server 10 to the client computing system 20 before starting video playback. This approach results in unacceptable delays for most video files, which are large. For example, even with transfer rates as fast as 1.5 Mb/second, the initial start-up delay is 60 seconds for a one minute video clip.
It is thus desirable to deliver video streams isochronously, as depicted in FIG. 2, so that video playback is guaranteed to have smooth motion and sound. The file server 10 must now transfer or stream the files 25 such that the time between each section of the file is transferred at a period of time τ. The even interval allows the file 25 to arrive isochronously with the first section to be displayed before any of the remaining sections of the file 25 have arrived at the client system 25. This allows a video clip to begin practically instantaneously.
The rapid advances in the speeds of microprocessors, storage, and network hardware may give a false impression that video on-demand (VOD) solutions do not need special purpose video streaming software. Video streaming as shown in FIG. 2 allows efficient playback of full motion videos over networks with guaranteed quality using isochronous timing.
When an operating system's default file transfer mode is used to stream a video file, faster hardware may accelerate the operating system's transfer rate, but this improved hardware still cannot change the fundamental, erratic behavior of a file transfer as shown in FIG. 1. By default, the file transfer process does not respect the isochronous nature of a video stream. This typically results in a jerky and poor-quality playback of a video stream. The dominant factors of a system's overall streaming performance are the higher level client/server and networking processes, and are not the raw power of the low level physical devices.
When an application at a Windows client accesses a file in a Windows NT server, the data is automatically cached by WFS at both Windows client and Windows NT server. This is a commonly used technique for reducing the amount of disk access when the cached data can be reused by subsequent requests. This technique does not work for most video-on-demand applications for two reasons. The first reason is that the cached data is hardly used again. VOD applications have very low “locality profile” because they tend to have high data rate and massive volume of videos for users' interactive playback. The second reason is that the constant video caching leads to intensive memory paging and, thus, severally limits performance.
U.S. Pat. No. 6,101,546 (Hunt) describes a method and system for providing data files that are partitioned by delivery time and data type. A file is logically partitioned into data channels where each data channels holds a sequence of data of a particular data type. The data channels are logically partitioned into delivery times. The format of the file explicitly sets forth the synchronization between the data channels and the delivery times of data held within the channels. The file format is especially well adapted for use in a distributed environment in which the file is to be transferred from a server to a client. Channel handlers are provided at the client to process respective data channels in the file. The channel handlers are data type specific in that they are constructed to process data of an associated data type. The data in the file may be rendered independently of the delivery time of the data.
U.S. Pat. No. 6,018,359 (Kermode, et al.) illustrates a system and method for multicast video-on-demand delivery system. The video-on-demand system divides video files into sequentially organized data segments for transmission and playback. Each segment is repeatedly transmitted in a looping fashion over a transmission channel. The rate of transmission is equal to or greater than the playback rate, and the lengths of the segments are chosen such that:                1. the receiver tunes into no more than a fixed number of channels (preferably two) at any one time;        2. the receiver tunes into a new channel only after an entire segment has been received from a previous channel; and        3. until a maximum segment length is attained, data is received from no fewer than two channels.        
The segments are sequentially presented even as new segments are being downloaded. When the display rate is equal to the transmission rate, it is found that the foregoing conditions are satisfied when the relative lengths of the segments form a modified Fibonacci sequence.
U.S. Pat. No. 5,930,473 (Teng, et al.) discloses a video application server for mediating live video services. The video application server is to be used in a network including source clients and viewer clients connected to one or more shared transmission media. A video server is connected to one of the transmission media and is operative to control the broadcast and storage of multiple live or previously-stored video streams. The control may be provided via remote procedure call (RPC) commands transmitted between the server and the clients. In one embodiment, a video presentation system is provided in which a video stream from a source client is continuously broadcast to a number of viewer clients. One or more of the viewer clients may be authorized by the source client to broadcast an audio and/or video stream to the other clients receiving the source video stream. In another embodiment, a multicast directory is provided to each of a plurality of viewer clients by transmitting directory information in a packet corresponding to a predetermined multicast address. The multicast directory indicates to a particular viewer client which of a number of video programs are available for broadcast to that client.
U.S. Pat. No. 6,101,547 (Mukherjee, et al.) describes an inexpensive, scalable and open-architecture media server. The multi-media server provides client systems with streaming data requiring soft real-time guarantee and static data requiring a large amount of storage space. The servers use a pull-mode protocol to communicate with client systems through a real-time network. Separate data and control channels enhance the soft real-time capability of the server. The data channel conforms to an open standard protocol such as such as Transmission Control Protocol (TCP), User Datagram Protocol (UDP), or Real-time Transport Protocol (RTP). A switched data link layer for the control channel permits separate intrahost control messages that may be multicast and broadcast. The distributed file system selects a specific data block size based upon the compression technique employed to enhance soft real-time guarantee. A hierarchical data structure combined with merging empty data blocks minimizes disk fragmentation. Data blocks are striped across multiple disks to improve disk utilization. A local buffer and a queue for both read and write requests provides support for simultaneous read and write data streams.
U.S. Pat. No. 5,805,821 (Saxena, et al.) teaches a video optimized media streamer user interface employing non-blocking switching to achieve isochronous data transfers. The media streamer includes at least one control node; a user interface having an output coupled to the at least one control node; at least one storage node for storing a digital representation of at least one video presentation; and a plurality of communication nodes each having an input port for receiving a digital representation of at least one video presentation therefrom. The video presentation requires a time T to present in its entirety, and is stored as a plurality of N data blocks. Each data block stores data corresponding to a T/N period of the video presentation. Each communication nodes further has a plurality of output ports for outputting a digital representation. A circuit switch is connected between the at least one storage node and the input ports of communication nodes for coupling one or more input ports to the at least one storage node. The user interface includes a capability for specifying commands for execution, and the at least one control node is responsive to individual ones of the commands for controlling at least one of the at least one storage node and at least one of the plurality of communication nodes, in cooperation with the circuit switch, so as to execute a function associated with individual ones of the commands. The commands may include video cassette recorder-like commands that include commands selected from a group that includes a Load command, an Eject command, a Play command, a Slow command, a Fast Forward command, a Pause command, a Stop command, a Rewind command, and a Mute command. The commands may also include commands selected from a group that includes a Play List command, a Play Length command, and a Batch command. A synchronous application program interface (API) is provided for coupling, via the user interface, a user application program to the at least one control node. The API includes Remote Procedure Call (RPC) procedures.
U.S. Pat. No. 5,550,577 (Verbiest, et al.) illustrates a video on demand network, including a central video server and distributed video servers with random access read/write memories. The video on demand network transmits video signals to user stations pursuant to the receipt of control signals issued by these user stations. In order to optimize the retrieval costs, this video on demand network maintains a large video library in a central video server and stores locally popular video signals in a plurality of local distributed video servers from which the latter video signals are transmitted to the user stations. The video signals provided by the local distributed servers are updated from the central server based upon the changing popularity of the video signals. The video on demand network of Verbiest proposes in particular to store the video signals in the local distributed servers in random access read/write memories, e.g., electronic RAMs, magnetic or optical disks from which the video signals can flexibly be supplied on-line to the user stations and to store the video signals in the central server in sequential access memories, e.g. Digital Audio Tapes (DAT) and CD-ROMs (CDR), providing cheap mass storage.
“Performance Evaluation of QuickVideo OnDemand (QVOD) Server,” InfoValue Computing, Inc. Technical Report IV-TR-QVOD-1999-07-1-1, Jul. 8, 1999, InfoValue Computing, Inc., Elmsford, N.Y. describes a video on-demand system developed for high performance, effective and flexible, network-based, on-demand sharing of videos. QuickVideo On Demand provides streaming throughput for broadband applications Further, QuickVideo On Demand allows a linearly scalable clustering mechanism which provides support for higher throughputs, if required. QuickVideo On Demand supports all video formats, codecs, networks and applications, and is compatible with any open application platform.
“Network Video Computing Via QuickVideo Suite,” InfoValue Technical White Paper, InfoValue Computing, Inc., Elmsford, N.Y., 1999, describes Network Video Computing the core of which is video streaming. Video streaming allows the efficient playing of full-motion video content over networks with guaranteed quality. The rigid timing property of full motion video is referred to as the isochronous timing. File servers are designed to minimize transfer latency during conventional network transfers, and are insensitive to video's unique timing requirement. As a result, delivery rates are irregular and produce erratic playback as described above. Video streaming technologies are real-time network transfers that maintain the video's critical timing property throughout the entire delivery period, as depicted in FIG. 2. This white paper describes the an open architecture with a streaming core.
“Web Distribution Systems: Caching and Replication” Chandbok, Ohio State University, 1999, found http://www.cis.ohio-state.edu/˜jain/cis788-99/web_caching/index.html, Aug. 15, 2000, provides an overview of the current techniques for caching and replication of digital data on computer systems interconnected through a global or local digital communication network. Refer now to FIG. 3 for a summary of caching in large distributed digital processing networks. Multiple server computing systems 100a, 100b, . . . , 100f are high performance computing systems such as the IBM Corporation RS-6000-SP, The Sun Microsystems, Inc. Enterprise 10000 Server, the Hewlett-Packard Netserver AA-6200, or other server systems The computer systems 100a, 100b, . . . , 100f are each connected to multiple storage devices 105a, 105b, . . . , 105r. The storage devices 105a, 105b, . . . , 105r are magnetic disk devices, compact disk read only memory (CD-ROM) “juke boxes,” or tapes drives. A group of the server systems 100a, 100b, 100c or 100d, 100e, 101f are respectively interconnected through the digital communications cluster network 110 and 115 to form the server cluster 1 120 and the server cluster 2 125. The server cluster 1 120 and the server cluster 2 125 may be resident with in the same enterprise data center or placed at different geographical locations either within the enterprises or even in different enterprises.
The cluster networks 110 and 115 are connected respectively to the network routers 130 and 135. The network routers 130 and 135 are further connected to a public or global digital communications network 155. The global network 155 may be the public Internet or an enterprise's private Intranet.
The server computer systems 100a, 100b, . . . , 100f contain database information systems, storage for files such as audio or video files, and other data files to accessed by large numbers of people either publicly or privately within an enterprise through the client systems 150a, 150b, 150c. 
Edge servers 140a, 140b, 140c are connected to the global network 155 and thus provide access portals for the client systems 150a, 150b, 150c to the global network 155 to communicate with each other, with other edge servers 140a, 140b, 140c, or with the server computer systems 100a, 100b, . . . , 100f. Each edge servers 140a, 140b, 140c is connected has attached data storage device 145a, 145b, . . . , 145i. The attached data storage device 145a, 145b, . . . , 145i is generally a magnetic disk storage device, but may also include a CD-ROM, magnetic tape, or other storage media.
If a server computer systems 100a, 100b, . . . , 100f has data 160 that is requested by many of the client systems 150a, 150b, 150c, the network traffic to the server computer system 100a may to great for either the global network 155 or the cluster network 110 to carry and maintain a reasonable quality of service. Quality of service in this context means that the original data 160 is transferred repetitively relatively quickly an if the original data 160 is audio or video files, that the isochronous nature of the transfer of the data is maintained.
If the server clusters 120 and 125 are separated geographically, it may cost less to maintain the quality of service by placing a copy 165 of the original data 160 in a disk 1051 on a second server system 100d. If the copy 165 of the original data 160 is permanent, it is referred to as being replicated. If the copy 165 of the original data 160 is temporary it is referred to as cached As the demand for the original data 160 is increased, it may be desirable to either replicate or cache 170 or 175 the data even within the disks 145b or 145i of the edge servers 150a or 150c. 
There are many policies developed regarding which of the original data 160 is replicated or cached 165, 170, or 175. Further, the replacement of cached data 165, 170, or 175 by other data that is demanded more often is known and generally follows a least recently used protocol, where the cached data 165, 170, or 175 that has not been requested is replaced by that is more requested.
U.S. Pat. No. 6,088,721 (Lin, et al.) teaches an efficient unified replication and caching protocol. The protocol provides assurance of consistent replication of objects from a central server to caching servers, for example, over data communication networks such as the Internet. It is an application-layer protocol, which guarantees delivery of objects such as files. This protocol insures that objects sent by a source machine such as a server to any number of destination machines such as caching servers actually arrive at the intended caching servers even when the caching servers are temporarily unavailable, for example, due to failure or network partition.
U.S. Pat. No. 6,061,504 (Tzelnic, et al.) illustrates a video file server using an integrated cached disk array and stream server computers. The video file server includes an integrated cached disk array storage subsystem and a multiple stream server computers linking the cached disk storage system to the data network for the transfer of video data streams. The video file server further includes a controller server for applying an admission control policy to client requests and assigning stream servers to service the client requests. The stream servers include a real-time scheduler for scheduling isochronous tasks, and supports at least one industry standard network file access protocol such as Simple Network Management Protocol (SNMP) and one file access protocol Network File System (NFS) for continuous media file access. The cached disk storage subsystem is responsive to video prefetch commands, and the data specified for a prefetch command for a process are retained in an allocated portion of the cache memory from the time that the cached disk storage subsystem has responded to the prefetch command to the time that the cached disk storage subsystem responds to a fetch command specifying the data for the process. The time between prefetching and fetching is selected based on available disk and cache resources. The video file server provides video-on-demand service by maintaining and dynamically allocating sliding windows of video data in the random access memories of the stream server computers.
“Network Caching Guide,” Goulde, Patricia Seybold Group for Inktomi Corp., Boston, Mass., March 1999, describes the various types of caching approaches and the different ways for caches to be implemented. Implementations vary depending on where the cache is placed, who is accessing the cache, and the quantity and type of content that is being cached. Goulde describes the Inktomi Traffic Server from Inktomi Corporation The Inktomi Traffic Server is capable of delivering fresh content to large numbers of users around the world from a large number of Web servers around the world.
“Inktomi Traffic Server—Media Cache Option”, Inktomi Corporation, San Mateo Calif., 1999, found http://www.inktomi.com, Aug. 15, 2000, describes the caching option for the Inktomi Traffic Server to support streaming of video data files.
“Implementing Multiplexing, Streaming, and Server Interaction for MPEG-4” Kalva et al., IEEE Transactions On Circuits And Systems For Video Technology, Vol. 9, No. 8, December 1999, pp. 1299–1312, describes the implementation of a streaming client-server system for object-based audio-visual presentations in general and MPEG-4 content in particular. The system augments the MPEG-4 demonstration software implementation (IM1) for PC's by adding network-based operation with full support for the Delivery Multimedia Integration Framework (DMIF) specification, a streaming PC-based server with DMIF support, and multiplexing software. The MPEG-4 server is designed for delivering object-based audio-visual presentations. The system also implements an architecture for client-server interaction in object-based audio-visual presentations, using the mechanism of command routes and command descriptors.
“New Solution for Transparent Web Caching: Traffic Server 2.1 Supports WCCP,” Inktomi Corporation, San Mateo Calif., 2000, found http://www.inktomi.com/products/network/traffic/tech/wccp, Aug. 15, 2000 describes the use of the Web Cache Control Protocol (WCCP) from Cisco Systems, Inc. within Inktomi Corporation's Traffic Server.
“API Overview,” Inktomi Corporation, San Mateo Calif., 2000, found http://www.inktomi.com/products/network/traffic/tech/wccp, Aug. 15, 2000, describes the application program interface tools that are available for the Inktomi Corporation's Traffic Server which allow customization or the Traffic Server's event processing thus allowing manipulation of hypertext transaction protocol (HTTP) transactions at any point in their lifetime.
“Web Cache Communication Protocol v2” Cisco Systems, Inc., San Jose, Calif., found http://www.cisco.com/univercd/cc/td/doc/product/software/ios120/120newft/120t/120t3/wccp.htm, Aug. 15, 2000, describes the protocol that allows the use a Cisco Cache Engine to handle web traffic, reducing transmission costs and downloading time. This traffic includes user requests to view pages and graphics on World Wide Web servers, whether internal or external to a network, and the replies to those requests When a user requests a page from a web server (located in the Internet), the router sends the request to a cache engine. If the cache engine has a copy of the requested page in storage, the cache engine sends the user that page. Otherwise, the cache engine retrieves the requested page and the objects on that page from the web server, stores a copy of the page and its objects, and forwards the page and objects to the user. WCCP transparently redirects Hypertext Transfer Protocol (HTTP) requests from the intended server to a cache engine.
“A Practical Methodology For Guaranteeing Quality Of Service For Video-On-Demand,” Zamora et al., IEEE Transactions On Circuits And Systems For Video Technology, Vol. 10, No. 1, February 2000, describes an approach for defining end-to-end quality of service (QoS) in video-on-demand (VoD) services. A schedulable region for a video server, which guarantees end-to-end QoS, where a specific QoS required in the video client, translates into a QoS specification for the video server. The methodology is based on a generic model for VoD services, which is extendible to any VoD system. In this kind of system, both the network and the video server are potential sources of QoS degradation. The effects that impairments in the video server and video client have on the video quality perceived by the end user is examined.
As described above, video files may be very large, on the order of 1.2 GB for a two hour movie or video presentation. In the digital communication networks 110, 115, and 155 of FIG. 3, the files are generally formed into data packets for transfer. These data packets may not arrive to a designated client system 150a, 150b, 150c in correct order for processing. This requires reception of the complete file before processing may begin. If the file is an audio or video file requiring isochronous presentation of the file, the files must be totally received before processing or the files must be segmented or partitioned into portions to allow smaller units of the files to be processed.
U.S. Pat. No. 5,926,649 (Ma, et al.) teaches a Media server for storage and retrieval of voluminous multimedia data. The Media server provides storage and retrieval of multiple data streams in a multimedia distribution system. A given data stream is separated into a plurality of portions, and the portions are stored in a multi-disk storage system with Y disks each having X zones such that the ith portion of the given stream is stored in zone (i mod X) of disk (i mod Y). The number X of zones per disk and the number Y of disks are selected as relatively prime numbers. The stored data are retrieved using Y independent retrieval schedulers, which are circulated among the Y disks over a number of scheduling intervals. Each retrieval scheduler processes multiple requests separated into X groups, with the requests of each group accessing the same disk zone during a given scheduling interval. The retrieval schedulers are also configured such that the retrieval requests of a given retrieval scheduler access the same disk during a given scheduling interval. The data stream placement technique in conjunction with the retrieval schedulers provide sequential-like parallel retrieval suitable for supporting real-time multimedia data distribution for large numbers of clients.
U.S. Pat. No. 5,936,659 (Viswanathan, et al.) illustrates a method for broadcasting movies within channels of a wide band network by breaking the communications path into a number of logical channels and breaking each movie up into a number of segments of increasing size. The first segment of each movie is the smallest segment is transmitted in sequence over the first logical channel and repeated. The second segment of each movie, which is proportionately larger than the first segment of each movie, is transmitted in sequence over the second logical channel and repeated. This is repeated for the total number of segments, which equals the total number of logical channels. The segments are broadcast in such a way that, once the first segment is received at a client location, the subsequent segments are also received in time, so that the movie can be viewed continuously.
U.S. Pat. No. 5,973,679 (Abbott, et al.) describes an indexing method for allowing a viewer to control the mode of delivery of program material. By mapping from time to data position, data delivery can begin at any selected time in the program material. The indexing method also provides for controlling data delivery to begin at the beginning of a frame of data. A synchronizing method is provided to minimize a time offset between audio and video data, particularly in environments using groups of pictures.
U.S. Pat. No. 5,996,015 (Day, et al.) describes a method of delivering seamless and continuous presentation of multimedia data files to a target device by assembling and concatenating multimedia segments in memory. The provides a multimedia server connected in a network configuration with client computer systems. The multimedia server further includes various functional units which are selectively operable for delivering and effecting the presentation of multimedia files to the client such that a plurality of multimedia files are seamlessly concatenated on the fly to enable a continuous and uninterrupted presentation to the client. In one example, client selected video files are seamlessly joined together at the server just prior to file delivery from the server. The methodology includes the analog to digital encoding of multimedia segments followed by a commonization processing to ensure that all of the multimedia segments have common operating characteristics. A seamless sequential playlist or dynamically created playlist is assembled from the selected and commonized segments and the resources needed to deliver and play the playlist are reserved in advance to assure resource availability for continuous transmission and execution of the playlist. At a predetermined point prior to an end point of each selected multimedia segment, the next selected segment is initialized and aligned in memory in preparation for a seamless switch to the next segment at the end of a previous segment, thereby providing a seamless flow of data and a continuous presentation of a plurality of selected multimedia files to a client system.
U.S. Pat. No. 5,608,448 (Smoral, et al.) describes a hybrid architecture for a video on demand server. The processing requirement at each computing element in a video server for a video on demand (VOD) system is reduced to only those needed for VOD, resulting in a less expensive processor with less memory and, hence, lower cost. A hybrid video server architecture combines the features of massive parallel processor (MPP) and workstation designs. Since it is not necessary to run a parallel relational database program in order to accomplish VOD data distribution, a unique type of switch element that is well matched to the VOD server problem is employed. By matching this switch element technology to an appropriate data storage technique, a full featured, responsive VOD server is realized.
U.S. Pat. No. 6,061,732 (Korst, et al.) describes a data streaming system utilizing an asynchronous technique for retrieving data from a stream server. In an audio/video server blocks of data are read from a storage medium by a reader and supplied to users in the form of data streams. The storage medium comprises a plurality of record-carrier based storage units. A reader reads a batch of data units from a storage unit in a single relative movement of a reading head of the storage unit with respect to the record-carrier of the storage unit. A scheduler controls reading of blocks from the storage medium by determining from which storage unit(s) data unit(s) need to be read for the block and placing a corresponding carrier access request in a read queue. The scheduler extracts for each of the storage units a batch of carrier access requests from the queue and issues the batch to the reader in an asynchronous manner, in response to the reader having substantially completed reading data units for a previous batch for the storage unit.
U.S. Pat. No. 5,414,455 (Hooper, et al.) teaches a segmented video on demand system. In the system for distributing videos, multiple videos are stored on a mass storage device. Each video includes a plurality of frames of digitized video data for play-back on a viewing device. The system includes a memory buffer for storing a segment of a selected one of the videos. The segment includes a predetermined number of frames representing a predetermined time interval of the selected video. In addition, the memory buffer including a write pointer and a read pointer. Software controlled servers are provided for witting and reading video data of the selected video to and from the memory buffer, independently, at locations indicated by the write and read pointers to transfer the selected video to the viewing device.
When any of the multiple client systems 150a, 150b, and 150c requests access to the original data 160 present, each request is fulfilled and the original data is routed through the server computing system 100a, the cluster network 110, the router 130, to the global digital communications network 155, to the edge servers 140a, 140b, 140c to the requesting client systems 150a, 150b, and 150c. Each transfer of the original data 160 consumes a portion of the available transfer rate (Bytes/sec) or bandwidth of the connections from the storage device 105a to the server computing system 100a, from the server computing system 100a to the cluster network 110, from the cluster network 110 to the router 130, from the router 130 to the global digital communication network 155, from the global communications network 155 to the edge servers 140a, 140b, 140c, from the edge servers 140a, 140b, 140c to the requesting client systems 150a, 150b, and 150c. The smallest bandwidth of this chain is generally the determining factor of the loading. In this case the loading determinant will be from the storage device 105a to the server computing system 100a. If there are no copies of the original data 160, as the number of requests for the original data increases, the available bandwidth decrease or loading on the storage device 105a increases. The loading of the data transfer 160 to and from the data storage device 105a must be in balance or the requests for the transfer may not be honored. In the case of video-on-demand, this cause interruptions or at least degradation of the quality of service in viewing the demanded video.
“DASD Dancing: A Disk Load Balancing Optimization Scheme for Video-on-Demand Computer,” Wolf, et al., ACM SIGMETRICS 1995, pp. 157–166 proposes a scheme to dynamically perform load-balancing of DASDs: (direct access storage devices), which is referred to as a DASD dancing algorithm. The algorithm consists of two components. The static component assigns movie files to DSGs (disk-striping groups) initially, and it also reassigns movies periodically, for example every day or every week. The dynamic component performs the real-time movie stream scheduling. (A disk-striping group, or DSG, is a group of disks, which contains a number of movies).
“Load Balancing For a Video-On-Demand Server,” DO, Information and Computer Science Dept, University of California, Irvine, 1998, found Oct. 1, 2000, http://www.ics.uci.edu/˜tdo/loadVOD/loadVOD.html, is an overview of the state of the art of load balancing for video-on-demand server systems, the problems that are involved with the server systems, and solutions for those problems.
“Random Duplicated Assignment: An Alternative to Striping in Video Servers,” Korst, Electronic Proceedings ACM Multimedia 97, November 1997, found http://info.acm.org/sigmm/MM97/Papers/korst/RDA.html, Oct. 2, 2000, describes an approach for storing video data in large disk arrays Video data is stored by assigning a number of copies of each data block to different, randomly chosen disks, where the number of copies may depend on the popularity of the corresponding video data. The use of the approach results in smaller response times and lower disk and RAM costs if many continuous variable-rate data streams have to be sustained simultaneously.
U.S. Pat. No. 5,544,313 (Shachnai, et al.) describes a baton passing optimization scheme for load balancing/configuration planning in a video-on-demand computer system. A video on demand computer system includes multiple storage devises each storing many video data files. The storage devices in this case are disks attached to a computer system. The computer system plays the videos on demand by reading out the videos from the disks as data streams to play selected video data files in response to user requests. The computer system is programmed to monitor the numbers of video data files being performed for each of the disks. Based on the monitoring function performed by the computer system, the computer system performs a load balancing function by transferring the current transfer of a video data file in progress from the disk having the original video data file being transferred to another disk having a copy of the video data file. The computer system periodically performs a reassignment function to transfer videos between the disks to optimize load balancing based on the user performance requests for each of the video data files. There are two phases to the load balancing performed by the computer system; a static phase and a dynamic phase. In the static phase, video data files are assigned to memory and disks, and in the dynamic phase there is provided a scheme for playing video data files with minimal and balanced loads on the disks. The static phase supports the dynamic phase, which insures optimal real-time operation of the system. Dynamic phase load balancing is accomplished by a process of “baton passing”.
“U.S. Pat. No. 5,333,315 (Saether, et al.) describe a computer system of device independent file directories using a tag between the directories and file descriptors that migrate with the files. The computer file system has a multiple disk storage devices which includes a multiple of file directories, stored on various disks. Each file directory is used to translate file names into corresponding tag values. For each disk there is a file descriptor table with a file descriptor entry for every file stored on the disk. A single tag directory contains one tag entry for every file stored in the system. The tag directory is used by the file system to find a file by translating a tag value into a pointer to the disk on which the file is stored and a pointer to the file's file descriptor entry. To move a file from a first disk to a second disk, the file is copied to the second disk, a new file descriptor entry for the copied file is generated in the file descriptor table for the second disk, the copy of the file on the first disk is de-allocated, and the tag entry for the file is updated to point to the second disk and to the file's new file descriptor entry. Thus, a file can be moved from a first disk a second without having to locate and update all the corresponding file directory entries. In a preferred embodiment, the file system includes a routine that monitors disk loading and unused disk capacity. It determines when disk usage is imbalanced and automatically moves files among the disks so as to better balance disk usage.
U.S. Pat. No. 5,631,694 (Aggarwal, et al.) describes a maximum factor selection policy for batching VOD requests. A VOD scheduler maintains a queue of pending performance for each video. Using the notion of queue selection factor, a batching policy is devised that schedules the video with the highest selection factor. Selection factors are obtained by applying discriminatory weighting factors to the adjusted queue lengths associated with each video where the weight decreases as the popularity of the respective video increases and the queue length is adjusted to take defection into account.